1. Technical Field
The invention relates to an apparatus for data compression, and more particularly, to such an apparatus employing a parallel analog processor.
2. Background Art
Data compression is the art of packing data. It is the process of transforming a body of data to a smaller representation from which the original or some approximation to the original can be retrieved at a later time. Most data sources contain redundancy like symbol distribution, pattern repetition, and positional redundancy. It is the role of the data compression algorithm to encode the data to reduce this built-in redundancy.
There are two kinds of data compression: lossless compression and lossy compression. Lossless compression guarantees that the data that is to be compressed and then subsequently decompressed, is identical to the original. Lossless data compression can be applied to any type of data. In practice, however, it is most common for textual data such as text, programming languages, object codes, data base information, numerical data, electronic mail etc., where it is important to preserve the original content exactly. Lossy data compression, on the other hand, allows the decompressed data to differ from the original data as long as the decompressed data can satisfy some fidelity criterion. For example, with image compression, it may suffice to have an image that subjectively looks to the human eye as good as the original. Likewise, in the case of compression of audio signals, it may suffice to have a reconstructed signal that merely sounds as good as the original to a user, rather than being an exact reproduction.
Data compression has not been a standard feature in most communication/storage systems for the following reasons: Compression increases the software and/or hardware cost; it is difficult to incorporate into high data rate systems (&gt;10 Mb/s); most compression techniques are not flexible enough to process different types of data; and blocks of compressed data with unpredictable lengths present space allocation problems. These obstacles are becoming less significant today due to the recent advances in algorithm development, high-speed VLSI technology, and packet switching communications. Data compression, in certain restricted applications, is now a feasible option for those communication or storage systems for which communication bandwidth and/or storage capacity are at a premium.
Of the numerous algorithms present in image coding, vector quantization has been used as a source coding technique for both speech and images. It essentially maps a sequence of continuous or discrete vectors into a digital sequence suitable for communication over a digital channel or storage in a digital medium. The goal is to reduce the volume of the data for transmission over a digital channel and also for archiving to a digital storage medium, while preserving the required fidelity of the data. This is particularly important to many present and future communication systems, as the volume of speech and image data in the foreseeable future would become prohibitively large for many communication links or storage devices. A major obstacle preventing the widespread use of such compression algorithms, is the large computational burden associated with the coding of such images. It has been shown that a well-designed vector quantization scheme can provide high compression ratio with good reconstructed quality. Insofar lies the motivation for this work.
Unlike scalar quantization where the actual coding of continuous or discrete samples into discrete quantities is done on single samples, the input data of a vector quantization encoder are multi-dimensional blocks of data (input vectors). Therefore, in image coding, raw pixels are grouped together as input vectors for post-processing by the encoder, as seen in FIG. 1. Without loss of generality, we shall refer to gray scale images. However, as will be apparent to those skilled in the art, compression of color images is readily dealt with by extension. In FIG. 1, a fraction of a gray scale image is shown with a block of pixels highlighted. In this case the dimensionality of the pixel block is 4.times.4, which is a typical value for vector quantization. In the pre-processing stage, the intensity values corresponding to the pixels in this 4.times.4 block are raster scanned into a 16 element vector for post- processing by the encoder. An important technique in vector quantization is the training of the codebook prior to transmission. Extensive preprocessing is performed on sample source data to construct the codebook which will be used in the compression session. The classical codebook training scheme is the Lloyd-Buzo-Gray (LBG) algorithm, which is a generalized k- mean clustering algorithm. There are various other means for generating a codebook with lower complexity. These include codeword merging and codeword splitting algorithms. These algorithms trade off lower rate-distortion performance for faster code book generation. The encoder and decoder must first agree on the same codebook before data transmission. The closeness between an input vector and a codeword in the codebook is measured by an appropriate distortion function. During the compression session distortions between an input vector and codewords in the codebook are evaluated. The codeword closest to the input vector is chosen as the quantization vector to represent the input vector. The index of this chosen codeword is then transmitted through the channel. Compression is achieved since fewer bits are used to represent the codeword index than the quantized input data. The decoder receives the codeword index, and reconstructs the transmitted data using the pre- selected codebook.
The vector quantization algorithm which provides the foundation for the VLSI based hardware solution associated with the present invention will now be discussed. Consider a k- dimensional VQ encoder. The source image, say from an image data file or directly from a CCD array, is to be divided up into non- overlapping squares of p*p pixels. The pixel intensities for the block are subsequently put into a raster scan order, i.e. a k-dimensional input vector given by EQU x=(x.sub.1, x.sub.2, . . . , x.sub.k) (1)
where k=p*p. The vector quantization encoder has an associated codebook C consisting of N precomputed codewords words given by: EQU C=C.sup.(1), C.sup.(2), . . . , C.sup.(N) ( 2)
In practice, N is some power of 2, ranging typically from 128 to 256 or even 512 vectors for a large codebook with lots of detail. The N codewords are of course k- dimensional, i.e. EQU C.sup.(i) =C.sub.k.sup.(i), C.sub.k.sup.(i), . . . ,C.sub.k.sup.(i)( 3)
For an input vector x, the encoder determines that codebook element C.sup.(m) such that EQU d(X, C.sup.(m)).ltoreq.d(, C.sup.(n)) (4)
for 1.ltoreq.n.ltoreq.N. The function d(X,C.sup.(m) is a distance metric, and the algorithmic goal is to find that codeword in the K dimensional space that is "closest" to the input vector. A common choice of the metric is the Euclidean distance metric, as given by ##EQU1## A more intuitive description of the problem is the following: For a k dimensional input vector consisting of bounded positive real-values and for a codebook consisting of N codewords, then the state space of the system is a k dimensional space populated by N unique vectors. The case for k=3 and N=6 is shown in FIG. 2. for illustrative purposes. The six stored codebook vectors are represented as filled points with indices C.sup.(i) in the 3 dimensional space. The input vector requiring classification is shown as the open point with index X. The role of the vector quantization encoder is to therefore select the physically closest codebook vector C.sup.(i) in the available space to the input vector X. The placement or selection of the locations of the codebook vectors is a part of the preprocessing stage and is outside the scope of this invention.
Once the encoder has determined the closest codeword for the given input kernel, all that remains is to either store or transmit the index m of the winning codeword. For a codebook consisting of N codewords, we require log.sub.2 N bits. On the receiving end, the decoder's job is to replace the index m by C.sup.(m). Therefore, the coder achieves a compression ratio of ##EQU2## where s is the number of bits per pixel. As an example, for an 8 bit/pixel gray scale image with a codebook size of 256 codewords, and using 16 dimensional kernels we achieve a compression ratio of 16.
In terms of the raw number of basic arithmetic operations (i.e. additions, multiplications, etc . . . ) required for each kernel classification, vector quantization is a very expensive algorithm to implement on a digital computer. There exist, however, techniques for pruning these prohibitive computational costs, but to date no such technique has lead to pseudo real-time image coding, hence the popularity of alternative coding schemes. Yet this very same repetitiveness of computations is indicative that the kernel classification task can be parallelized.
It is, therefore, an objective of the present invention to demonstrate how such a parallelization of the vector quantization algorithm was achieved.
In addition, it is another objective of the present invention to demonstrate how the parallelization of the vector quantization algorithm can be embodied in VLSI hardware.